Celestin Apprentice 7/Apprentice-Release7.iso/Environments/PowerLisp 2.01/Supplemental Documentation/Documentation/Chapter 03. Scope and Extent

Lisp/Scheme | 1995-03-27 | 15KB | 323 lines

Common Lisp the Language, 2nd Edition
-------------------------------------------------------------------------------

3. Scope and Extent

In describing various features of the Common Lisp language, the notions of
scope and extent are frequently useful. These notions arise when some object or
construct must be referred to from some distant part of a program. Scope refers
to the spatial or textual region of the program within which references may
occur. Extent refers to the interval of time during which references may occur.

As a simple example, consider this program:

(defun copy-cell (x) (cons (car x) (cdr x)))

The scope of the parameter named x is the body of the defun form. There is no
way to refer to this parameter from any other place but within the body of the
defun. Similarly, the extent of the parameter x (for any particular call to
copy-cell) is the interval from the time the function is invoked to the time it
is exited. (In the general case, the extent of a parameter may last beyond the
time of function exit, but that cannot occur in this simple case.)

Within Common Lisp, a referenceable entity is established by the execution of
some language construct, and the scope and extent of the entity are described
relative to the construct and the time (during execution of the construct) at
which the entity is established. For the purposes of this discussion, the term
``entity'' refers not only to Common Lisp data objects, such as symbols and
conses, but also to variable bindings (both ordinary and special), catchers,
and go targets. It is important to distinguish between an entity and a name for
the entity. In a function definition such as

(defun foo (x y) (* x (+ y 1)))

there is a single name, x, used to refer to the first parameter of the
procedure whenever it is invoked; however, a new binding is established on
every invocation. A binding is a particular parameter instance. The value of a
reference to the name x depends not only on the scope within which it occurs
(the one in the body of foo in the example occurs in the scope of the function
definition's parameters) but also on the particular binding or instance
involved. (In this case, it depends on the invocation during which the
reference is made). More complicated examples appear at the end of this
chapter.

There are a few kinds of scope and extent that are particularly useful in
describing Common Lisp:

   *  Lexical scope. Here references to the established entity can occur only
     within certain program portions that are lexically (that is, textually)
     contained within the establishing construct. Typically the construct will
     have a part designated the body, and the scope of all entities established
     will be (or include) the body.

     Example: the names of parameters to a function normally are lexically
     scoped.

   *  Indefinite scope. References may occur anywhere, in any program.

   *  Dynamic extent. References may occur at any time in the interval between
     establishment of the entity and the explicit disestablishment of the
     entity. As a rule, the entity is disestablished when execution of the
     establishing construct completes or is otherwise terminated. Therefore
     entities with dynamic extent obey a stack-like discipline, paralleling the
     nested executions of their establishing constructs.

     Example: the with-open-file construct opens a connection to a file and
     creates a stream object to represent the connection. The stream object has
     indefinite extent, but the connection to the open file has dynamic extent:
     when control exits the with-open-file construct, either normally or
     abnormally, the stream is automatically closed.

     Example: the binding of a ``special'' variable has dynamic extent.

   *  Indefinite extent. The entity continues to exist as long as the
     possibility of reference remains. (An implementation is free to destroy
     the entity if it can prove that reference to it is no longer possible.
     Garbage collection strategies implicitly employ such proofs.)

     Example: most Common Lisp data objects have indefinite extent.

     Example: the bindings of lexically scoped parameters of a function have
     indefinite extent. (By contrast, in Algol the bindings of lexically scoped
     parameters of a procedure have dynamic extent.) The function definition

     (defun compose (f g)
       #'(lambda (x)
           (funcall f (funcall g x))))

     when given two arguments, immediately returns a function as its value. The
     parameter bindings for f and g do not disappear because the returned
     function, when called, could still refer to those bindings. Therefore

     (funcall (compose #'sqrt #'abs) -9.0)

     produces the value 3.0. (An analogous procedure would not necessarily work
     correctly in typical Algol implementations or, for that matter, in most
     Lisp dialects.)

In addition to the above terms, it is convenient to define dynamic scope to
mean indefinite scope and dynamic extent. Thus we speak of ``special''
variables as having dynamic scope, or being dynamically scoped, because they
have indefinite scope and dynamic extent: a special variable can be referred to
anywhere as long as its binding is currently in effect.

[change_begin]
The term ``dynamic scope'' is a misnomer. Nevertheless it is both traditional
and useful.
[change_end]

The above definitions do not take into account the possibility of shadowing.
Remote reference of entities is accomplished by using names of one kind or
another. If two entities have the same name, then the second may shadow the
first, in which case an occurrence of the name will refer to the second and
cannot refer to the first.

In the case of lexical scope, if two constructs that establish entities with
the same name are textually nested, then references within the inner construct
refer to the entity established by the inner one; the inner one shadows the
outer one. Outside the inner construct but inside the outer one, references
refer to the entity established by the outer construct. For example:

(defun test (x z)
  (let ((z (* x 2))) (print z))
  z)

The binding of the variable z by the let construct shadows the parameter
binding for the function test. The reference to the variable z in the print
form refers to the let binding. The reference to z at the end of the function
refers to the parameter named z.

In the case of dynamic extent, if the time intervals of two entities overlap,
then one interval will necessarily be nested within the other one. This is a
property of the design of Common Lisp.

-------------------------------------------------------------------------------
Implementation note: Behind the assertion that dynamic extents nest properly is
the assumption that there is only a single program or process. Common Lisp does
not address the problems of multiprogramming (timesharing) or multiprocessing
(more than one active processor) within a single Lisp environment. The
documentation for implementations that extend Common Lisp for multiprogramming
or multiprocessing should be very clear on what modifications are induced by
such extensions to the rules of extent and scope. Implementors should note that
Common Lisp has been carefully designed to allow special variables to be
implemented using either the ``deep binding'' technique or the ``shallow
binding'' technique, but the two techniques have different semantic and
performance implications for multiprogramming and multiprocessing.
-------------------------------------------------------------------------------

A reference by name to an entity with dynamic extent will always refer to the
entity of that name that has been most recently established that has not yet
been disestablished. For example:

(defun fun1 (x)
  (catch 'trap (+ 3 (fun2 x))))

(defun fun2 (y)
  (catch 'trap (* 5 (fun3 y))))

(defun fun3 (z)
  (throw 'trap z))

Consider the call (fun1 7). The result will be 10. At the time the throw is
executed, there are two outstanding catchers with the name trap: one
established within procedure fun1, and the other within procedure fun2. The
latter is the more recent, and so the value 7 is returned from the catch form
in fun2. Viewed from within fun3, the catch in fun2 shadows the one in fun1.
Had fun2 been defined as

(defun fun2 (y)
  (catch 'snare (* 5 (fun3 y))))

then the two catchers would have different names, and therefore the one in fun1
would not be shadowed. The result would then have been 7.

As a rule, this book simply speaks of the scope or extent of an entity; the
possibility of shadowing is left implicit.

The important scope and extent rules in Common Lisp follow:

   *  Variable bindings normally have lexical scope and indefinite extent.

[change_begin]

   *  Variable bindings for which there is a dynamic-extent declaration also
     have lexical scope and indefinite extent, but objects that are the values
     of such bindings may have dynamic extent. (The declaration is the
     programmer's guarantee that the program will behave correctly even if
     certain of the data objects have only dynamic extent rather than the usual
     indefinite extent.)

   *  Bindings of variable names to symbol macros by symbol-macrolet have
     lexical scope and indefinite extent.

[change_end]

   *  Variable bindings that are declared to be special have dynamic scope
     (indefinite scope and dynamic extent).

[change_begin]

   *  Bindings of function names established, for example, by flet and labels
     have lexical scope and indefinite extent.

   *  Bindings of function names for which there is a dynamic-extent
     declaration also have lexical scope and indefinite extent, but function
     objects that are the values of such bindings may have dynamic extent.

   *  Bindings of function names to macros as established by macrolet have
     lexical scope and indefinite extent.

   *  Condition handlers and restarts have dynamic scope (see chapter 29).

[change_end]

   *  A catcher established by a catch or unwind-protect special form has
     dynamic scope.

   *  An exit point established by a block construct has lexical scope and
     dynamic extent. (Such exit points are also established by do, prog, and
     other iteration constructs.)

   *  The go targets established by a tagbody, named by the tags in the
     tagbody, and referred to by go have lexical scope and dynamic extent.
     (Such go targets may also appear as tags in the bodies of do, prog, and
     other iteration constructs.)

   *  Named constants such as nil and pi have indefinite scope and indefinite
     extent.

The rules of lexical scoping imply that lambda-expressions appearing in the
function construct will, in general, result in ``closures'' over those
non-special variables visible to the lambda-expression. That is, the function
represented by a lambda-expression may refer to any lexically apparent
non-special variable and get the correct value, even if the construct that
established the binding has been exited in the course of execution. The compose
example shown earlier in this chapter provides one illustration of this. The
rules also imply that special variable bindings are not ``closed over'' as they
may be in certain other dialects of Lisp.

Constructs that use lexical scope effectively generate a new name for each
established entity on each execution. Therefore dynamic shadowing cannot occur
(though lexical shadowing may). This is of particular importance when dynamic
extent is involved. For example:

(defun contorted-example (f g x)
  (if (= x 0)
      (funcall f)
      (block here
         (+ 5 (contorted-example g
                                 #'(lambda ()
                                     (return-from here 4))
                                 (- x 1))))))

Consider the call (contorted-example nil nil 2). This produces the result 4.
During the course of execution, there are three calls on contorted-example,
interleaved with two establishments of blocks:

(contorted-example nil nil 2)

  (block here   ...)

    (contorted-example nil #'(lambda () (return-from here   4)) 1)

      (block here   ...)

        (contorted-example #'(lambda () (return-from here   4))
                           #'(lambda () (return-from here   4))
                           0)
          (funcall f)
                where f => #'(lambda () (return-from here   4))

            (return-from here   4)

At the time the funcall is executed there are two block exit points
outstanding, each apparently named here. In the trace above, these exit points
are distinguished for expository purposes by subscripts. The return-from form
executed as a result of the funcall operation refers to the outer outstanding
exit point (here  ), not the inner one (here  ). This is a consequence of the
rules of lexical scoping: it refers to that exit point textually visible at the
point of execution of the function construct (here abbreviated by the #'
syntax) that resulted in creation of the function object actually invoked by
the funcall.

If, in this example, one were to change the form (funcall f) to (funcall g),
then the value of the call (contorted-example nil nil 2) would be 9. The value
would change because the funcall would cause the execution of (return-from here
   4), thereby causing a return from the inner exit point (here  ). When that
occurs, the value 4 is returned from the middle invocation of
contorted-example, 5 is added to that to get 9, and that value is returned from
the outer block and the outermost call to contorted-example. The point is that
the choice of exit point returned from has nothing to do with its being
innermost or outermost; rather, it depends on the lexical scoping information
that is effectively packaged up with a lambda-expression when the function
construct is executed.

This function contorted-example works only because the function named by f is
invoked during the extent of the exit point. Block exit points are like
non-special variable bindings in having lexical scope, but they differ in
having dynamic extent rather than indefinite extent. Once the flow of execution
has left the block construct, the exit point is disestablished. For example:

(defun illegal-example ()
  (let ((y (block here #'(lambda (z) (return-from here z)))))
    (if (numberp y) y (funcall y 5))))

One might expect the call (illegal-example) to produce 5 by the following
incorrect reasoning: the let statement binds the variable y to the value of the
block construct; this value is a function resulting from the lambda-expression.
Because y is not a number, it is invoked on the value 5. The return-from should
then return this value from the exit point named here, thereby exiting from the
block again and giving y the value 5 which, being a number, is then returned as
the value of the call to illegal-example.

The argument fails only because exit points are defined in Common Lisp to have
dynamic extent. The argument is correct up to the execution of the return-from.
The execution of the return-from is an error, however, not because it cannot
refer to the exit point, but because it does correctly refer to an exit point
and that exit point has been disestablished.